\documentclass{article}

\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage{setspace}
\usepackage{graphicx}
%%%%%%%%%%%%%%%% Lengths %%%%%%%

%%%%%%%%%
\setlength{\textwidth}{15.5cm}
\setlength{\evensidemargin}{0.5cm}
\setlength{\oddsidemargin}{0.5cm}

%%%%%%%%%%%%%%%% Variables %%%%%%%%%%%%%%%%
\title{Projet de système d'exploitation}
\author{Emmanuel Seunes, Mathilde Oustlant, Niels Montanari, Quentin Maouhoub, Vincent Loubet}
\date{9 mai 2012}

\begin{document}

%%%%%%%%%%%%%%%% Header %%%%%%%%%%%%%%%%
%\begin{center}
%\textbf{{\LARGE\titre}}
%\end{center}

\maketitle
\newpage
\tableofcontents
\newpage
%\vspace*{10mm}
%\fbox{
%  Membres : \responsible \\
%}

%%%%%%%%%%%%%%%% Main part %%%%%%%%%%%%%%%%

\section*{Introduction}

Le projet de système d'exploitation consiste en la création d'une bibliothèque de gestion de threads, alternative aux pthreads.

\section{Structures de données}

Chaque thread est représenté par une structure constituée de quatre champs :
\begin{itemize}
\item son contexte ;
  \item sa valeur de retour ;
  \item l'éventuel thread en attente de sa terminaison ;
  \item la localisation mémoire de sa pile, pour valgrind.\\
\end{itemize}
\\
\begin{figure}[h]
\includegraphics[width=\linewidth]{Dessinsanstitre.png}
\end{figure}

\\
Deux listes globales sont utilisées pour l'ordonnancement des threads : la \textit{run queue} et la \textit{death queue}. Ce sont des listes doublement chaînées circulaires.

Les ajouts et suppressions de thread au sein de ces listes se font donc en temps constant.\\

Les threads en attente d'exécution ainsi que le thread en cours d'exécution sont stockés dans une \textit{run queue}.
Le thread pointé par la \textit{run queue} correspond au thread en cours d'exécution, le thread suivant au prochain thread à exécuter et le thread précédent au dernier thread en attente d'exécution. 

L'accès au prochain thread à exécuter se fait, en particulier, en temps constant.\\

Les threads terminés sont stockés, au besoin, dans la \textit{death queue}. Ils sont conservés dans cette liste jusqu'au moment où un thread fait un appel à \textit{thread\_join}, de manière à ce que celui-ci puisse récupérer la valeur de retour du thread terminé.

La recherche d'un thread dans la liste se fait en temps linéaire.\\

\section{Fonctions de gestion des threads}

\subsection{thread\_create}

Deux cas de figure se présentent lors d'un appel à \textit{thread\_create} selon que la \textit{run queue} existe ou non, i.e. selon qu'un premier appel à \textit{thread\_create} ou \textit{thread\_self} ait été effectué ou non.
 
Dans le premier cas, la \textit{run queue} nécessite d'être créée avant que le thread nouvellement créé ainsi que celui du \textit{main}, également créé, y soient ajoutés.

Dans le second cas, le thread nouvellement créé peut immédiatement être ajouté à la \textit{run queue}.\\

Le thread nouvellement créé est ensuite activé grâce à un changement de contexte.

\subsection{thread\_self}

Deux cas de figure se présentent lors d'un appel à \textit{thread\_self} selon que la \textit{run queue} existe ou non, i.e. selon qu'un premier appel à \textit{thread\_create} ou \textit{thread\_self} ait été effectué ou non.

Dans le premier cas, la \textit{run queue} nécessite d'être créée et le thread du \textit{main}, également créé, y est ajouté. La valeur du pointeur du thread du \textit{main} est retournée.

Dans le second cas, la valeur du pointeur du thread en cours d'exécution, correspondant au thread pointé par la \textit{run queue}, est retournée.\\

\subsection{thread\_yield}

\textit{thread\_yield} décale simplement le pointeur de la \textit{run queue} vers le thread suivant et réalise le changement de contexte. 

Si la \textit{run queue} n'existe pas ou que celle-ci ne contient qu'un seul thread, ces opérations sont ignorées. Un coûteux et inutile changement de contexte est ainsi évité.

\subsection{thread\_join}

\textit{thread\_join} commence par vérifier s'il n'y a pas déjà un thread en attente de la valeur de retour du thread passé en paramètre. Si tel est le cas, \textit{thread\_join} retourne immédiatement, avec une valeur indiquant qu'il y a déjà un thread en attente de la valeur de retour.\\

Deux possibilités se présentent suivant si le thread attendu a terminé, suite à un appel à \textit{thread\_exit}, ou non.

S'il a terminé, le thread est trouvé dans la \textit{death queue}, sous réserve que celle-ci existe. Il y est supprimé et sa valeur de retour est récupérée.

Sinon, le thread n'est pas trouvé dans la \textit{death queue} ou celle-ci n'existe pas. Le thread courant est alors mémorisé dans la structure du thread attendu comme étant en attente de sa valeur de retour et est enlevé de la \textit{run queue}. Un changement de contexte s'effectue enfin pour endormir le thread courant, permettant ainsi une attente passive.  

\subsection{thread\_exit}

Lors d'un \textit{thread\_exit}, la valeur de retour est stockée.\\

Si le thread courant a un thread en attente de sa terminaison, celui-ci est réveillé, i.e. il est placé dans la \textit{run queue}. Le thread courant y est quand à lui supprimé.

Dans le cas contraire, le thread courant est transferé de la \textit{run queue} vers la \textit{death queue}, en ayant créé celle-ci si elle n'existait pas auparavant.\\

Enfin, le thread suivant est activé via un changement de contexte.

\section{Fonctions des Mutex}

Le premier objectif avancé implémenté est l'utilisation de mutex pour la synchronisation.\\

Un mutex est repésenté en mémoire par un pointeur, servant aussi d'indentifiant, qui pointe vers une structure.
Celle-ci contient un verrou d'acquisition du mutex, la valeur du mutex et une \textit{queue} contenant les threads en attente du déverrouillage du mutex.\\

Pour anticiper l'implémentation d'une version multicœur, un verrou d'acquisition du mutex différent de la valeur du mutex est utilisé. Ainsi, le caractère atomique des opérations effectuées sur le mutex est garanti.
En effet, il suffit de rendre l'opération d'acquisition du mutex atomique pour garantir l'absence de conflit entre les threads.\\

La librairie OpenPA a été utilisée pour réaliser cette opération atomique. Cette librairie propose la fonction \textit{OPA\_cas\_int}(entier \textit{OPA}, valeur supposée de l'entier, nouvelle valeur de l'entier), qui change la valeur d'un entier en la valeur souhaitée si ce dernier a la valeur supposée en paramètre. De plus, \textit{OPA\_cas\_int} retourne la nouvelle valeur de l'entier \textit{OPA}.\\

Le verrou du mutex est un entier OPA qui a pour valeur \textit{UNLOCK} ou \textit{LOCK}. Pour prendre possession du mutex, il suffit donc de boucler sur la fonction \textit{OPA\_cas\_int} pour tenter de passer l'entier de \textit{UNLOCK} à \textit{LOCK} jusqu'a ce qu'elle réussisse. 

Pas de solution n'a été trouvée pour éviter l'attente active engendrée. Cependant, les fonctions des mutex se produisant en temps constant, cette attente peut raisonnablement être supposée négligeable.

\subsection{thread\_mutex\_init}

Le type d'un mutex étant un pointeur, il est nécessaire d'allouer sa structure.\\

La fonction \textit{thread\_mutex\_init} permet de créer la structure du mutex et d'initialiser ses attributs. 
Le verrou d'acquisition du mutex est défini à ouvert. Par analogie avec les mutex de pthread, la valeur du mutex est passée à déverrouillé.

\subsection{thread\_mutex\_destroy}

La structure du mutex étant alloué dynamiquement, il est nécessaire de pouvoir la libérer.\\

\textit{thread\_mutex\_destroy} permet de le faire.
Pour ce faire, une attente active s'effectue jusqu'à prendre possession du mutex, puis l'abscence de thread en attente du mutex dans la \textit{queue} est vérifiée. Cela garantit qu'aucun thread n'utilise le mutex lors de sa destruction, et évite donc des erreurs et fuites mémoires.

\subsection{thread\_mutex\_lock}

\textit{thread\_mutex\_lock} permet de vérrouiller le mutex et, s'il est déjà vérrouillé, d'attendre de façon passive son déverrouillage.\\

S'il n'est pas verrouillé, il en prend possession et changer la valeur du mutex.\\

Si, par contre, une fois le mutex pris possession, celui-ci se révèle déjà verrouillé, le thread se met dans la queue d'attente du mutex, se retire de la \textit{run queue} et procède à un changement de contexte. Il passe ainsi en attente passive et sera reveillé par un autre thread. Il réessaiera alors de verrouiller le mutex.\\

\subsection{thread\_mutex\_trylock}

\textit{thread\_mutex\_trylock} fonctionne comme \textit{thread\_mutex\_lock} à la différence qu'il n'y a pas de mise en attente passive. Le mutex étant verrouillé, il renvoie simplement la valeur \textit{EBUSY} à l'utilisateur.\\

\subsection{thread\_mutex\_unlock}

\textit{thread\_mutex\_unlock} permet de déverrouiller un mutex une fois sont acquisition faite.\\

De plus, si l'un des thread est en attente dans la \textit{queue} du mutex, il enlève le premier thread en attente de pouvoir verrouiller le mutex et le place aprés lui dans la \textit{run queue}.\\

Le choix de placer le thread en attente du mutex en second dans la runq est discutable : il double un autre thread alors qu'il aurait pu être placé à la fin de la \textit{run queue}. Cependant, ce thread ayant rendu la main plus vite que le temps escompté, il lui est donné une compenstion par rapport au temps passé dans la \textit{queue} d'attente du mutex.

\section{Préemption}

De par son importance, la préemption constitue le deuxième objectif avancé à avoir été implémenté. L'utilisateur doit pouvoir bénéficier d'une utilisation tranparente des threads et de leur ordonnancement.\\

La préemption s'effectue grâce à un gestionnaire de signaux initialisé en même temps que le thread du main. Lorsque le gestionnaire reçoit un signal \textit{SIGVTALRM}, il effectue un changement de contexte de manière similaire à \textit{thread\_yield}.\\

L'envoi de signaux est géré grâce à la fonction \textit{setitimer} de la façon suivante : 
\begin{itemize}
\item Le timer est arrêté et sauvegardé à l'entrée d'une fonction thread.
\item Avant d'effectuer un changement de contexte, on vérifie que la \textit{runqueue} contienne plus d'un élément, afin d'éviter une coûteuse et inutile interruption. Si tel est le cas, la préemption est relancée avec une nouvelle slice de temps .
\item Aprés avoir effectué un changement de contexte ne débouchant pas sur la sortie de la fonction, le timer est sauvegardé là aussi.
\item Lorsque la sortie d'une fonction thread n'est pas précédée d'un changement de contexte, le timer est relancé avec la valeur précedemment sauvegardée. La fonction \textit{thread\_self} ne consommera donc pas de temps sur le timer de préemption.\\
\end{itemize}
La sauvegarde du temps utilisé dans une fonction avant un changement de contexte étant faite, il est envisageable de faire de l'ordonnancement en fonction de la portion de la slice de temps utilisée par un thread.
Pour ce faire, un fonctionnement proche de celui de l'ordonnancement par priorité à base de queues multiples a été pensé, mais le temps à manquer pour la mettre en place.

\section{Test de fonctionnement}

\subsection{Fonctionnement normal}

Le premier test effectué consiste au lancement du programme d'exemple en affichant l'évolution de la \textit{run queue} et de la \textit{death queue}.\\

Le comportement des threads est bien celui escompté et le passage des threads dans la \textit{death queue} et la \textit{run queue} peut être remarqué :

\begin{verbatim}
le main lance 2 threads...
Runq:This q is empty   //Le main et seul
Deathq:This q is empty
Runq:This q containt : //On a lancé le 1er thread
0x155a3d0              //thread 1             
join : (nil)
0x155a7f0              //main
join : (nil)
Deathq:This q is empty
je suis le thread 0x155a3d0, lancé avec l'argument thread1
Runq:This q containt : //Le main reprend la main
0x155a7f0              //main
join : (nil) 
0x155a3d0              //thread 1
join : (nil)
Deathq:This q is empty
Runq:This q containt : //On a lancé le 2eme thread
0x156ac00              //thread 2
join : (nil)
0x155a3d0              //thread 1
join : (nil)
0x155a7f0              //main
join : (nil)
Deathq:This q is empty
je suis le thread 0x156ac00, lancé avec l'argument thread2
Runq:This q containt : //Le thread 2 passe la main au thread 1
0x155a3d0              //thread 1
join : (nil)
0x155a7f0              //main
join : (nil)
0x156ac00              //thread 2
join : (nil)
Deathq:This q is empty
je suis encore le thread 0x155a3d0, lancé avec l'argument thread1
le main a lancé les threads 0x155a3d0 et 0x156ac00
Runq:This q containt : //Le thread 1 fini et a passé la main au main
0x155a7f0              //main
join : (nil)
0x156ac00              //thread 2
join : (nil)
Deathq:This q containt :
0x155a3d0              //thread 1 qui a fini
join : (nil)
le main attend les threads
Runq:This q containt : //Le main a fait le 1er join
0x155a7f0              //main
join : (nil)
0x156ac00              //thread 2
join : (nil)
Deathq:This q is empty
Runq:This q containt : //Le main c'est endormit et a passé la main
0x156ac00              //thread 2
join : 0x155a7f0       //main qui attend le thread 2
Deathq:This q is empty
je suis encore le thread 0x156ac00, lancé avec l'argument thread2
Runq:This q containt : //Le main est bien reveillé pour le join
0x155a7f0              //main
join : (nil)
Deathq:This q is empty
les threads ont terminé en renvoyant 'thread1' and 'thread2'
\end{verbatim}

\subsection{Fonctionnement des mutex}

De même, pour les mutex, 2 threads ont été utilisés, l'un bouclant sur l'incrémentation et l'autre sur la décrémentation d'une même variable globale initialisée à 0. Suite à quoi, ils appellent la fonction \textit{thread\_yield}. Les threads terminent en affichant la valeur de la variable globale. Le thread d'incrémentation est lancé en premier et boucle 10000 fois ; le thread de décrémentation boucle 5000 fois.
Ces threads ont été lancés une première fois sans mutex, puis avec le verrouillage / déverrouillage d'un mutex autour de la boucle \textit{for}.
Les résultats sont bien ceux escomptés :

\begin{verbatim}
Nouvelle valeur calculé sans mutex par dec :1
Nouvelle valeur calculé sans mutex par add :5000

Nouvelle valeur calculé avec mutex par add :10000
Nouvelle valeur calculé avec mutex par dec :5000
\end{verbatim}

\subsection{Fonctionnement de la préemption}

Pour tester la préemption, 3 threads bouclant en attente active dans une boucle \textit{for}, incrémentant un entier et affichant respectivement "titi", "tata" et "toto" sont utilisés. Les threads "titi" et "toto" bouclent comme cela 300 fois et le thread "tata" boucle 400 fois. De plus, un affichage lors de la rentrée dans la fonction de préemption a été ajouté.
On obtient bien un entrelacement de "titi" / "tata" / "toto" limités par la préemption, puis uniquement "titi" sans préemption :  

\begin{verbatim}
//Au milieu de l'execution :
75 Titi
Préemption
77 Tata
78 Tata
Préemption
76 Toto
77 Toto
Préemption
76 Titi
77 Titi
Préemption
79 Tata
80 Tata
Préemption
78 Toto
//A la fin de l'execution
297 Titi
Préemption
298 Toto
299 Toto  //changement de contexte grâce à thread_exit 
298 Titi
299 Titi
300 Titi
301 Titi
302 Titi
303 Titi
304 Titi
305 Titi
\end{verbatim}

\section{Test de perfomance}

\subsection{Gestion de la mémoire}

Pour tester l'efficacité mémoire de l'implémentation, plusieurs tests comparatifs avec pthread ont été réalisés.\\

Le premier consite à lancer un thread (qui incrémente un entier puis retourne) et à l'attendre. On affiche alors avec \textit{valgrind} l'utilisation de la mémoire en fonction du nombre de fois que l'opération ait été effectuée. On obtient alors les résultats suivant :

\begin{verbatim}
Pthread:
all:total heap usage: 6 allocs, 6 frees, 1,862 bytes allocated

Thread:
1:total heap usage: 9 allocs, 5 frees, 67,552 bytes allocated
10:total heap usage: 54 allocs, 50 frees, 666,520 bytes allocated
100:total heap usage: 504 allocs, 500 frees, 6,656,200 bytes allocated
1000:total heap usage: 5,004 allocs, 5,000 frees, 66,553,000 bytes allocated
10000:total heap usage: 50,004 allocs, 50,000 frees, 665,521,000 bytes allocated
\end{verbatim}

Il faut remarquer que pthread utilise la même quantité de mémoire quelque soit le nombre de fois que l'on lance un thread. 
La fuite mémoire, de 1000 octets, est dûe à la non libération du thread du main. Une fonction de libération du thread du main a d'ailleurs été implémentée à cet effet.

Très logiquement, on peut aussi noter que la consommation mémoire est bien directement proportionnelle au nombre de threads lancés. De manière équivalente, la consommation mémoire par thread est constante et est d'environ  66,5 ko. \\

La consommation mémoire générale quand un seul thread est lancé à un instant donné est de 67,5 ko. La consommation mémoire pour lancer un unique thread est donc plus de 37 fois supérieure à celle de pthread à un instant donné. \\

Une solution possible pour réduire la consommation serait de ne pas détruire les threads et de les placer dans une file d'attente, afin de les réutiliser une fois sortis de la \textit{deathqueue}.
La structure des \textit{queue} peut également être modifiée, avec notamment l'ajout d'un champ suivant et de l'état à la structure des threads. Ceci baisserait les perfomances mais diminurerait la consommation mémoire.
\newpage

\subsection{Suite de Fibonacci}

Pour tester les performances de l'implémentation, un calcul de la suite de Fibonacci a été implémenté d'une façon naïve qui crée un thread à chaque appel récursif. La fonction \textit{time} est utilisée pour mesurer le temps mis pour que le calcul termine et des moyennes sur 5 itérations ont été effectuées. Les résultats obtenus sont les suivants : \\

\begin{figure}[h]
\includegraphics[width=\linewidth]{graphique_1.png}
\caption{Temps d'exécution du calcul de la suite de Fibonacci}
\end{figure}

On peut ici noter que les performances sont meilleures que celles de pthread.
Il est aussi intéressant de noter le détail de \textit{time}. En effet, la version pthread passe la grande majorité de son temps à exécuter des appels systèmes, tandis que notre version passe majoritairement son temps du coté utilisateur.


\section*{Conclusion}

L'exécution du programme d'exemple se fait de la même manière qu'avec pthread. La rotation des threads suit bien les algorithmes implémentés et les valeurs de retour des threads sont correctement récupérées. De plus, l'attente dûe au \textit{thread\_join} est une attente passive. Cette fonction gère les tentatives de \textit{thread\_join} multiples, bien que la valeur de retour ne soit récuperable qu'une seule fois. Finalement, toute la mémoire utilisée sauf celle du thread du main est bien libérée. Les mutex ont également été mis en place ; ils sont compatibles avec une utilisation multiprocesseur et permettraient d'implémenter facilement des sémaphores. De plus, l'attente de déverrouillage d'un thread a été rendue passive. La préemption a également été implémentée en faisant attention à ne l'enclencher que lorsqu'il y a plus d'un thread pouvant s'exécuter.\\
Ce projet aura était une expérience trés intéressante que nous aurions aimé pousser plus loin. Malheureusement, la disparité de niveau au sein du groupe a été un frein pour l'implémentation de davantages d'améliorations, malgré les nombreuse idées de poursuite.

\end{document}
